Search engines generate revenue by publishing advertisements that are believed to be relevant to queries set forth by users. Typically, an advertisement is selected for presentment on a search engine results page (SERP) based upon an auction for an advertisement position on the SERP. With more particularity, a search engine receives a query that includes at least one keyword, and advertisers set forth bids for an advertisement position (within which their advertisements can be displayed) based upon the keyword. Thus, each advertisement participating in the auction has a bid value and a click probability value assigned thereto, wherein a click probability is indicative of a probability that a user will select an advertisement if presented in the advertisement position, given that the user has set forth the keyword. The search engine then computes scores for advertisements based upon the bids and click probabilities for the advertisements.
An advertisement that wins the auction is the advertisement that has a highest score assigned thereto from amongst all scores computed for the advertisement position. This winning advertisement is then presented in the advertisement position on the SERP returned to the user. The generalized second price (GSP) auction mechanism is typically used to compute a price to be paid by the advertiser (who manages an ad campaign that includes the advertisement) if the user selects (clicks) the advertisement. The above-described auction mechanism has relied on two fundamental assumptions that pertain to fair selection of advertisements and pricing for advertisements: 1) separability; and 2) independence. Separability refers to the assumption that positional effect on the click probability of an advertisement is able to be modeled as a simple multiplier on a click probability of the advertisement at any specific location. Thus, if a click probability of the advertisement at a first (most prominent) position at the top of the SERP is known, the click probability at any advertisement position can be determined from a known click probability curve. Independence refers to the assumption that the click probability of an advertisement is independent of what is shown around it. These assumptions, however, do not always hold, particularly in view of advertising techniques that are used by some advertisers, but not others.